// Package _5_I_二叉树的深度 main
// @Title _5_I_二叉树的深度
// @Description
// @Author  == 琳琳也叫王木木 ==  2022-01-13 19:43
// @Create  2022-01-13 19:43
package main

import "fmt"

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func main() {
	root := TreeNode{
		3,
		&TreeNode{
			9, nil, nil,
		},
		&TreeNode{
			20, &TreeNode{15, nil, nil},
			&TreeNode{7, nil, nil},
		},
	}
	fmt.Println(maxDepthBFS(&root))
}

//
//  maxDepth
//  @Description: 获取二叉树的深度 使用层序遍历的方式
//  @param root： 二叉树的根节点
//  @return int： 二叉树的深度
//
func maxDepthBFS(root *TreeNode) int {
	if root == nil {
		return 0
	}
	depth := 0
	queue := []*TreeNode{root}
	for len(queue) > 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			tNode := queue[0]
			queue = queue[1:]
			if tNode.Left != nil {
				queue = append(queue, tNode.Left)
			}
			if tNode.Right != nil {
				queue = append(queue, tNode.Right)
			}
		}
		depth++
	}
	return depth
}

//
//  maxDepthDFS
//  @Description: 使用DFS的形式获取二叉树的深度
//  @param root：二叉树的根节点
//  @return int： 二叉树的深度(层高)
//
func maxDepthDFS(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return max(maxDepthDFS(root.Left), maxDepthDFS(root.Right)) + 1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
